﻿using System.Text;

namespace Graph;

public class DiAdjLinkList : IDiGraph
{
    
    private LinkedList<int>[] graph; //记录每个顶点的所有邻接点组成的链表

    public int V { get; }
    public int E { get; }    

    public DiAdjLinkList(string file)
    {
        StreamReader sr = new StreamReader(file);

        string line = sr.ReadLine();
        string[] str = line.Split(' ');

        V = int.Parse(str[0]);
        E = int.Parse(str[1]);

        //空间复杂度 O（V+E）
        graph = new LinkedList<int>[V];
        for (int i = 0; i < V; i++)
        {
            graph[i] = new LinkedList<int>();
        }

        //建图时间复杂度 O（E）
        for (int i = 0; i < E; i++)
        {
            line = sr.ReadLine();
            str = line.Split(' ');

            int a = int.Parse(str[0]);
            int b = int.Parse(str[1]);

            //有向图
            graph[a].AddLast(b);
            //graph[b].AddLast(a);
        }
        
        sr.Close();
    }

    //查看两点是否相邻 O（1）
    public bool HasEdge(int a, int b)
    {
        return graph[a].Contains(b);
    }

    //求一个点的相邻顶点集 O（1）
    public IEnumerable<int> Adj(int a)
    {
        return graph[a];
    }

    //顶点a的相邻点数 O（1）
    public int Degree(int a)
    {
        return Adj(a).Count();
    }

    public int InDegree(int a)
    {
        return InAdj(a).Count();
    }

    public int Degrees(int a)
    {
        return Degree(a) + InDegree(a);
    }

    public IEnumerable<int> InAdj(int a)
    {
        List<int> res = new List<int>();

        for (int b = 0; b < V; b++)
        {
            if (HasEdge(b,a))
            {
                res.Add(b);
            }
        }

        return res;
    }

    //打印图信息，输出邻接表
    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();

        sb.Append($"V = {V}, E={E}\n");
        for (int a = 0; a < V; a++)
        {
            sb.Append(a + " : ");
            foreach (var b in graph[a])
            {
                sb.Append(b + " ");
            }
            sb.Append("\n");
        }

        return sb.ToString();
    }

    //验证
    static void Main(string[] args)
    {
        IGraph graph = new DiAdjLinkList("有向无权图/无环图.txt");
        Console.WriteLine(graph);

        //Console.WriteLine(graph.HasEdge(0, 1));

        //var adjs = graph.Adj(0);
        //foreach (var v in adjs)
        //{
        //    Console.Write(v + " ");
        //}
        //Console.WriteLine();

        //Console.WriteLine(graph.Degree(0));

        Console.Read();
    }
}
